Any communications system (e.g., computer network) must utilize a protocol for determining the sequence and nature of the permitted communications over the system. In the past, protocols for star networks have generally been those which were developed for other networks such as rings or buses. For example, it is known to operate star networks on the basis of token passing protocols that were originally developed for ring networks. With such protocols, a logical "token" is passed from station to station and any station "holding" the token is allowed to transmit data. A disadvantage of token passing protocols is that the gap (measured in bits) between the end of transmission by one station and the beginning of transmission by the next station to receive the token increases with the data rate. This overhead, due to passing the token, places both a lower bound on the access delay and an upper bound on the efficiency of utilization of the system, and, in addition, limits the efficiency under low loading. Thus, token passing protocols are not efficient on a star network.
Star networks have also been operated using random access protocols, such as CSMA/CD (Carrier Sense Multiple Access/Collision Detect). However, with such protocols, the minimum length of a transmission by a station must increase with the data rate, and this produces inefficiency. An increase in data rate is not compensated for by a reduction in access delay, since the number of "collisions" between data from different stations will remain approximately constant.
Another known type of protocol for broadcast communications systems is the so-called "bit-map" protocol. Bit-map protocols have previously been used, for example, in packet radio systems. Typically, in a bit-map protocol the stations reserve the use of subsequent slots in an operating cycle by setting an appropriate bit in a reservation field (or bit-map). The stations thereafter use their reserved slots to transmit data. As the stations are part of a broadcast system, the bit-map is available to all stations to enable them to judge when they should transmit their data during the main part of the operating cycle.
It is also known to have two transmissions present at the same time on different branches of a tree-configured telephone network. In the known arrangement, the local telephone exchange determines the distance from the exchange of each user and then asks each user to transmit its data at a time calculated to avoid collisions with other users, but possibly at a time that results in more than one transmission being simultaneously present on the network. This system, however, is based upon a central intelligence that is not employed in systems of the type to which the present invention is directed, i.e., systems in which each station has its own intelligence.
An object of the present invention is to provide a communications system employing a modified bit-map protocol that can be used to advantage in a star network. It is a further object of the present invention to provide a communication system employing a modified bit-map protocol that can be used to advantage in network topologies other than star topologies. It is a still further object of the present invention to provide a communication system whereby more than one transmission can be present on the network at a time. The present invention achieves these goals.